package leetcode;

import util.NodeQ0116.Node;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/22 16:54
 */
public class Q0117 {
    /**
     * O(N) O(N)
     */
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> q = new LinkedList<>();
        HashMap<Node, Integer> map = new HashMap<>();
        q.add(root);
        map.put(root, 0);
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (!q.isEmpty() && Objects.equals(map.get(node), map.get(q.peek()))) node.next = q.peek();
            if (node.left != null) {
                q.add(node.left);
                map.put(node.left, map.get(node) + 1);
            }
            if (node.right != null) {
                q.add(node.right);
                map.put(node.right, map.get(node) + 1);
            }
        }
        return root;
    }
}
